<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <title>min_lcost_flow1</title>
  </head>
  <body bgcolor="#FFFFFF">
    <center>Scilab function</center>
    <div align="right">Last update : September 1995</div>
    <p>
      <b>min_lcost_flow1</b> -  minimum linear cost flow</p>
    <h3>
      <font color="blue">Calling Sequence</font>
    </h3>
    <dl>
      <dd>
        <tt>[c,phi,flag] = min_lcost_flow1(g)  </tt>
      </dd>
    </dl>
    <h3>
      <font color="blue">Parameters</font>
    </h3>
    <ul>
      <li>
        <tt>
          <b>g</b>
        </tt>: graph list</li>
      <li>
        <tt>
          <b>c</b>
        </tt>: value of cost</li>
      <li>
        <tt>
          <b>phi</b>
        </tt>: row vector of the value of flow on the arcs</li>
      <li>
        <tt>
          <b>flag</b>
        </tt>: feasible problem flag (0 or 1)</li>
    </ul>
    <h3>
      <font color="blue">Description</font>
    </h3>
    <p>
      <tt>
        <b>min_lcost_flow1</b>
      </tt> computes the minimum linear cost flow in the network 
    <tt>
        <b>g</b>
      </tt>. It returns the total cost of the flows on the arcs <tt>
        <b>c</b>
      </tt> and
    the row vector of the flows on the arcs <tt>
        <b>phi</b>
      </tt>. If the problem is not 
    feasible (impossible to find a compatible flow for instance), <tt>
        <b>flag</b>
      </tt> is 
    equal to 0, otherwise it is equal to 1.</p>
    <p>
    The bounds of the flow are given by the elements <tt>
        <b>edge_min_cap</b>
      </tt> and
    <tt>
        <b>edge_max_cap</b>
      </tt> of the graph list. 
    The value of the minimum capacity and of the maximum capacity must be non 
    negative and must be integer numbers.
    The value of the maximum capacity must be greater than or equal to the 
    value of the minimum capacity.
    If the value of <tt>
        <b>edge_min_cap</b>
      </tt> or <tt>
        <b>edge_max_cap</b>
      </tt> is not given (empty
    row vector <tt>
        <b>[]</b>
      </tt>), it is assumed to be equal to 0 on each edge.</p>
    <p>
    The costs on the edges are given by the element <tt>
        <b>edge_cost</b>
      </tt> of the 
    graph list.
    The costs must be non negative.
    If the value of <tt>
        <b>edge_cost</b>
      </tt> is not given (empty row vector <tt>
        <b>[]</b>
      </tt>), 
    it is assumed to be equal to 0 on each edge.</p>
    <p>
    The demands, element <tt>
        <b>node_demand</b>
      </tt> of the graph list, must be
    equal to zero.</p>
    <p>
    This function uses the out-of-kilter algorithm.</p>
    <h3>
      <font color="blue">Examples</font>
    </h3>
    <pre>

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10 1 8];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1 12 14];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g('node_y')=[56 221 316 318 316 143 214 321 217 126 215 80 330 437 439];
show_graph(g);
g1=g;ma=arc_number(g1);
rand('uniform');
while %T then
  g1('edge_min_cap')=round(20*rand(1,ma));
  g1('edge_max_cap')=round(20*rand(1,ma))+g1('edge_min_cap')+33*ones(1,ma);
  g1('edge_cost')=round(10*rand(1,ma))+ones(1,ma);
  [c,phi,flag]=min_lcost_flow1(g1);
  if flag==1 then break; end;
end;  
x_message(['The cost is: '+string(c);
           'Showing the flow on the arcs ']);
ii=find(phi&lt;&gt;0); edgecolor=phi; edgecolor(ii)=11*ones(ii);
g1('edge_color')=edgecolor;
edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii);
g1('edge_font_size')=edgefontsize;
g1('edge_label')=string(phi);
show_graph(g1);
 
  </pre>
    <h3>
      <font color="blue">See Also</font>
    </h3>
    <p>
      <a href="min_lcost_cflow.htm">
        <tt>
          <b>min_lcost_cflow</b>
        </tt>
      </a>,&nbsp;&nbsp;<a href="min_lcost_flow2.htm">
        <tt>
          <b>min_lcost_flow2</b>
        </tt>
      </a>,&nbsp;&nbsp;<a href="min_qcost_flow.htm">
        <tt>
          <b>min_qcost_flow</b>
        </tt>
      </a>,&nbsp;&nbsp;</p>
  </body>
</html>
